package com.cong.leetcode.sort;

public class QuickSort {
    public int[] sort(int[] nums) {
        recurSort(nums, 0, nums.length -1 );
        return nums;
    }
    public void recurSort(int[] nums, int p, int r) {
        if (p < r) {
            int q = partition(nums, p, r);
            recurSort(nums, p, q - 1);
            recurSort(nums, q + 1, r);
        }
    }
    private int partition(int[] nums, int p, int r) {
        int k = nums[r];
        int i = p - 1;
        int temp;
        for (int j = p; j < r; j++) {
            if (nums[j] <= k) {
                i++;
                temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
            }
        }

        temp = nums[i+1];
        nums[i+1] = nums[r];
        nums[r] = temp;
        return i + 1;
    }

    private void innerIterQuickSort(int[] nums, int left, int right) {

    }

    public int[] iterQuickSort(int[] nums) {

        return nums;
    }
}
